#include<iostream>
#include<vector>
#include<stack>
using namespace std;

struct TreeNode {
 int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        stack<TreeNode*> stack_[2];
        stack_[0].push(NULL);
        while (root1 != NULL) {
            stack_[0].push(root1);
            root1 = root1->left;
        }
        stack_[1].push(NULL);
        while (root2 != NULL) {
            stack_[1].push(root2);
            root2 = root2->left;
        }

        vector<int>res;
        while (stack_[0].top()!=NULL || stack_[1].top()!=NULL) {
            TreeNode* node1 = stack_[0].top();
            TreeNode* node2 = stack_[1].top();
            int which = 1;
            TreeNode* node= node2;
            if (node1!=NULL&&node2 != NULL) {
                if (node1->val < node2->val) {
                    which = 0;
                    node = node1;
                    res.push_back(node1->val);
                }
                else
                    res.push_back(node2->val);
            }
            else if (node1 != NULL) {
                which = 0;
                node = node1;
                res.push_back(node1->val);
            }
            else {
                res.push_back(node2->val);
            }
            stack_[which].pop();
            node = node->right;
            while (node != NULL) {
                stack_[which].push(node);
                node = node->left;
            }
        }
        return res;
    }
};